1. Field of the Invention
Aspects of the present invention relate to a method of and an apparatus for generating a parity check matrix, and more particularly, to a method of and an apparatus for generating a block-based low-density parity check (LDPC) matrix, which facilitates parity bit generation.
2. Description of the Related Art
To generate additional information for error correction, an LDPC coding method is widely used. The LDPC coding involves generating parity bits using an LDPC matrix H having 0s and 1s, in which a number of 1s is far less than a number of 0s.
The number of 1s included in each row or column of a parity check matrix is referred to as a row degree or a column degree. A regular parity check matrix indicates a parity check matrix in which row degrees of all the rows are the same or column degrees of all the columns are the same. An irregular parity check matrix indicates a parity check matrix in which row degrees of all the rows are not the same or column degrees of all the columns are not the same. In a regular parity check matrix, a row degree is referred to as a row weight (Wr) and a column degree is referred to as a column weight (Wc).
The generation of parity bits using LDPC coding is performed according to equation 1.HX=0  (1)
In equation 1, H represents a parity check matrix of m*n and X represents a codeword matrix of n*1, wherein X is composed of a message data vector S having a length of (n−m) and a parity bit vector P having a length of m. Thus, a sum of the length (n−m) of the message data vector S and the length (m) of the parity bit vector P is equal to n.
A concept of LDPC coding has been disclosed by D. J. MacKay in “Good Error-Correction Codes Based on Very Sparse Matrices” (IEEE Trans. on Information Theory, vol. 45, no.2, pp. 399-431, 1999). According to Mackay, parity bits can be generated by calculating Equation 1 using a matrix operation such as Gaussian elimination. However, in the case of LDPC coding, since a code length is large and the size of the parity check matrix H is also large, encoding using Gaussian elimination requires very complicated computation.
To solve the problem, an efficient coding method for transforming a parity check matrix into another format has been developed by T. J. Richardson and is referred to as a Richardson method. FIG. 1 illustrates a format of a parity check matrix that is transformed through the Richardson method.
According to the Richardson method, the parity check matrix H is transformed into a transformed parity check matrix H′ through row interchange and column interchange. After the transformation, a top right corner portion 100 of the transformed parity check matrix H′ should be composed of only 0s, as shown in FIG. 1. In other words, the transformed parity check matrix H′ is composed of areas A, B, C, D, E, and T, and the top right corner portion 100 of the area T is composed of only 0s.
According to the Richardson method, since t elements of the top right corner portion 100 of the transformed parity check matrix H′ all are 0s, t parity bits can be easily obtained through back substitution, facilitating a generation of parity information. However, to obtain (m−t) parity bits, inverse matrix calculation is required. The remaining (m−t) parity bits can be obtained as follows.
Equation 1 is transformed into Equation 2 using the Richardson method.
                    Hx        =                                            H              ′                        ⁢            x                    =                                    [                                                                    A                                                        B                                                        T                                                                                        C                                                        D                                                        E                                                              ]                        ⁡                          [                                                                    S                                                                                                              P                      1                                                                                                                                  P                      2                                                                                  ]                                                          (        2        )            
In Equation 2, S represents a message data vector and P1 and P2 represent a first parity bit vector and a second parity bit vector, respectively. Equation 2 is expressed as matrix equations 3 and 4.AS+BP1+TP2=0, CS+DP1+EP2=0  (3)(−ET−1A+C)S+(−ET−1B+D)P1=(−ET−1A+C)S+φP1=0  (4)
In equations (3) and (4), a Richardson matrix φ=(−ET−1B+D). By combining Equations 3 and 4, the first parity bit vector P1 and the second parity bit vector P2 can be defined in Equations 5 and 6, respectively.P1=−(−ET−1B+D)−1(−ET−1A+C)S=−φ−1(−ET−1A+C)S  (5)P2=−T−1(AS+BP1)  (6)
According to the Richardson method, although t parity bits can be easily obtained through back substitution, since an inverse matrix, i.e., φ−1, needs to be calculated to obtain the remaining (m−t) parity bits, parity bit generation is not easy. A more thorough discussion of the Richardson Method may be found in an article entitled “Efficient Encoding of Low-Density Parity Check Codes,” Thomas J. Richardson and Rudiger L. Urbanke, IEEE Transactions on Information Theory, Vol. 47, No. 2, pp. 638-656, 2001.
FIG. 2 illustrates a conventional block based LDPC matrix based on blocks b, each having a predetermined number of 1s in each column and each row. In FIG. 2, one diagonal matrix is formed in an area T using unit matrix blocks, and unit matrix blocks and shift matrix blocks are arranged randomly in areas A, C, B, D, and E.
Thus, parity bits corresponding to blocks included in the area T may be easily obtained through back-substitution. However, since unit matrix blocks and shift matrix blocks are arranged randomly in the area E defined as a gap, an inverse matrix φ−1 still needs to be calculated to obtain parity bits corresponding to blocks of the areas E and D, making parity bit generation difficult.